package 链表;

/**
 * @ClassName : _92_反转链表2_双指针头插法
 * @Author : 骆发茂
 * @Date: 2021/12/9 11:24
 * @Description : https://leetcode-cn.com/problems/reverse-linked-list-ii/
 */
public class _92_反转链表2_双指针头插法 {
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode reverseBetween(ListNode head, int left, int right) {
            ListNode fakenode = new ListNode(0);
            fakenode.next = head;

            ListNode pre = fakenode;
            ListNode cur = fakenode.next;

            for(int step=0;step++<left-1;){
                pre = pre.next;
                cur = cur.next;
            }
            for(int i=0;i++<right-left;){
                ListNode temp  = cur.next;
                //连接后面
                cur.next = cur.next.next;

                //头插法
                temp.next = pre.next;
                pre.next = temp;
            }

            return fakenode.next;


        }
    }
}